package LinkedList;

public class _109_ConvertSortedListtoBinarySearchTree {
    public TreeNode sortedListToBST(ListNode head) {
        if(head==null) return null;
        if(head.next==null) return new TreeNode(head.val);
        ListNode middle = getMiddle(head);
        TreeNode root = new TreeNode(middle.val);
//        root.left = (head==null?null:new TreeNode(getMiddle(head).val));
//        root.right =(middle.next==null?null:new TreeNode(getMiddle(middle.next).val));
            root.left = sortedListToBST(head);
            root.right = sortedListToBST(middle.next);
        return root;
    }

    public ListNode getMiddle(ListNode head){
        if(head==null) return null;
        ListNode slow = head,fast = head;
        ListNode preSlow = head;
        while(fast.next!=null && fast.next.next!=null){
            fast = fast.next.next;
            preSlow = slow;
            slow = slow.next;
        }
        ListNode middle = null;
        //while the listnode length is 2,if the middle is in the left,the up function will be in dead circle,
        //so the middle assign to the right value
        if(fast.next!=null){
            middle = slow.next;
            slow.next = null;
        }else{
            middle = slow;
            preSlow.next = null;
        }
        return middle;
    }
}
